<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>字符串解码算法详解</title>
    <link href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css" rel="stylesheet">
    <link href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css" rel="stylesheet">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
        }
        .serif-font {
            font-family: 'Noto Serif SC', serif;
        }
        .gradient-text {
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
            -webkit-background-clip: text;
            -webkit-text-fill-color: transparent;
            background-clip: text;
        }
        .card-hover {
            transition: all 0.3s ease;
        }
        .card-hover:hover {
            transform: translateY(-4px);
            box-shadow: 0 20px 40px rgba(0,0,0,0.1);
        }
        .code-block {
            background: linear-gradient(135deg, #1e1e2e 0%, #2d2d44 100%);
            border-radius: 12px;
            overflow: hidden;
        }
        .code-header {
            background: rgba(255,255,255,0.05);
            padding: 12px 20px;
            border-bottom: 1px solid rgba(255,255,255,0.1);
        }
        pre {
            margin: 0;
            padding: 20px;
            overflow-x: auto;
        }
        code {
            font-family: 'Consolas', 'Monaco', 'Courier New', monospace;
            line-height: 1.6;
        }
        .drop-cap {
            float: left;
            font-size: 4rem;
            line-height: 1;
            font-weight: 700;
            margin-right: 8px;
            margin-top: -8px;
            color: #667eea;
        }
        .highlight-box {
            background: linear-gradient(135deg, #f5f7fa 0%, #c3cfe2 100%);
            border-left: 4px solid #667eea;
            padding: 20px;
            border-radius: 8px;
            margin: 20px 0;
        }
        .mermaid {
            display: flex;
            justify-content: center;
            margin: 40px 0;
        }
    </style>
</head>
<body class="bg-gray-50">
    <!-- Hero Section -->
    <section class="relative overflow-hidden bg-gradient-to-br from-purple-600 via-indigo-600 to-blue-600 text-white">
        <div class="absolute inset-0 bg-black opacity-20"></div>
        <div class="relative container mx-auto px-6 py-24">
            <div class="max-w-4xl mx-auto text-center">
                <h1 class="text-5xl md:text-6xl font-bold mb-6 serif-font">
                    字符串解码算法
                </h1>
                <p class="text-xl md:text-2xl mb-8 opacity-90">
                    <i class="fas fa-code mr-2"></i>
                    巧用栈结构解决括号嵌套问题
                </p>
                <div class="flex justify-center space-x-4">
                    <span class="inline-flex items-center px-4 py-2 bg-white bg-opacity-20 rounded-full text-sm">
                        <i class="fas fa-layer-group mr-2"></i>栈
                    </span>
                    <span class="inline-flex items-center px-4 py-2 bg-white bg-opacity-20 rounded-full text-sm">
                        <i class="fas fa-clock mr-2"></i>O(n)
                    </span>
                    <span class="inline-flex items-center px-4 py-2 bg-white bg-opacity-20 rounded-full text-sm">
                        <i class="fas fa-brain mr-2"></i>中等难度
                    </span>
                </div>
            </div>
        </div>
        <div class="absolute bottom-0 left-0 right-0">
            <svg viewBox="0 0 1440 120" fill="none" xmlns="http://www.w3.org/2000/svg">
                <path d="M0 120L60 110C120 100 240 80 360 70C480 60 600 60 720 65C840 70 960 80 1080 85C1200 90 1320 90 1380 90L1440 90V120H1380C1320 120 1200 120 1080 120C960 120 840 120 720 120C600 120 480 120 360 120C240 120 120 120 60 120H0V120Z" fill="#F9FAFB"/>
            </svg>
        </div>
    </section>

    <!-- Main Content -->
    <main class="container mx-auto px-6 py-12 max-w-6xl">
        <!-- Problem Description -->
        <section class="mb-16">
            <div class="bg-white rounded-2xl shadow-lg p-8 card-hover">
                <h2 class="text-3xl font-bold mb-6 flex items-center">
                    <i class="fas fa-puzzle-piece mr-3 text-indigo-600"></i>
                    <span class="gradient-text">题目描述</span>
                </h2>
                <p class="text-lg leading-relaxed text-gray-700">
                    <span class="drop-cap serif-font">给</span>定一个经过编码的字符串，返回它解码后的字符串。编码规则为: <code class="bg-gray-100 px-2 py-1 rounded text-purple-600 font-mono">k[encoded_string]</code>，表示其中方括号内部的 encoded_string 正好重复 k 次。
                </p>
                <div class="highlight-box mt-6">
                    <p class="font-semibold text-gray-800 mb-2">
                        <i class="fas fa-lightbulb mr-2 text-yellow-500"></i>
                        示例
                    </p>
                    <ul class="space-y-2 text-gray-700">
                        <li><code class="bg-gray-100 px-2 py-1 rounded font-mono">3[a]</code> → <code class="bg-green-100 px-2 py-1 rounded font-mono text-green-700">aaa</code></li>
                        <li><code class="bg-gray-100 px-2 py-1 rounded font-mono">2[abc]</code> → <code class="bg-green-100 px-2 py-1 rounded font-mono text-green-700">abcabc</code></li>
                        <li><code class="bg-gray-100 px-2 py-1 rounded font-mono">3[a2[c]]</code> → <code class="bg-green-100 px-2 py-1 rounded font-mono text-green-700">accaccacc</code></li>
                    </ul>
                </div>
            </div>
        </section>

        <!-- Algorithm Visualization -->
        <section class="mb-16">
            <div class="bg-white rounded-2xl shadow-lg p-8">
                <h2 class="text-3xl font-bold mb-8 flex items-center">
                    <i class="fas fa-sitemap mr-3 text-indigo-600"></i>
                    <span class="gradient-text">算法流程图</span>
                </h2>
                <div class="mermaid">
                    graph TD
                        A[开始遍历字符串] --> B{当前字符类型?}
                        B -->|数字| C[累加数字值]
                        B -->|左括号 '[' | D[入栈当前状态]
                        B -->|右括号 ']'| E[出栈并构建字符串]
                        B -->|字母| F[添加到当前字符串]
                        C --> G[继续遍历]
                        D --> H[重置当前状态]
                        E --> I[重复字符串并拼接]
                        F --> G
                        H --> G
                        I --> G
                        G --> J{遍历结束?}
                        J -->|否| B
                        J -->|是| K[返回结果]
                        
                        style A fill:#e0e7ff,stroke:#6366f1,stroke-width:2px
                        style K fill:#d1fae5,stroke:#10b981,stroke-width:2px
                        style B fill:#fef3c7,stroke:#f59e0b,stroke-width:2px
                </div>
            </div>
        </section>

        <!-- Solution Approach -->
        <section class="mb-16">
            <div class="grid md:grid-cols-2 gap-8">
                <div class="bg-white rounded-2xl shadow-lg p-8 card-hover">
                    <h3 class="text-2xl font-bold mb-4 flex items-center">
                        <i class="fas fa-lightbulb mr-3 text-yellow-500"></i>
                        核心思路
                    </h3>
                    <ul class="space-y-4">
                        <li class="flex items-start">
                            <i class="fas fa-check-circle text-green-500 mt-1 mr-3"></i>
                            <div>
                                <p class="font-semibold text-gray-800">双栈结构</p>
                                <p class="text-gray-600">使用两个栈分别存储数字（重复次数）和字符串</p>
                            </div>
                        </li>
                        <li class="flex items-start">
                            <i class="fas fa-check-circle text-green-500 mt-1 mr-3"></i>
                            <div>
                                <p class="font-semibold text-gray-800">括号匹配</p>
                                <p class="text-gray-600">遇到 '[' 入栈，遇到 ']' 出栈并构建</p>
                            </div>
                        </li>
                        <li class="flex items-start">
                            <i class="fas fa-check-circle text-green-500 mt-1 mr-3"></i>
                            <div>
                                <p class="font-semibold text-gray-800">状态维护</p>
                                <p class="text-gray-600">维护当前字符串和当前数字两个状态</p>
                            </div>
                        </li>
                    </ul>
                </div>
                
                <div class="bg-gradient-to-br from-indigo-50 to-purple-50 rounded-2xl shadow-lg p-8 card-hover">
                    <h3 class="text-2xl font-bold mb-4 flex items-center">
                        <i class="fas fa-chart-line mr-3 text-indigo-600"></i>
                        复杂度分析
                    </h3>
                    <div class="space-y-6">
                        <div>
                            <p class="font-semibold text-gray-800 mb-2">
                                <i class="fas fa-clock mr-2 text-blue-500"></i>
                                时间复杂度
                            </p>
                            <p class="text-3xl font-bold text-indigo-600">O(n)</p>
                            <p class="text-gray-600 mt-1">每个字符只被访问一次</p>
                        </div>
                        <div>
                            <p class="font-semibold text-gray-800 mb-2">
                                <i class="fas fa-memory mr-2 text-purple-500"></i>
                                空间复杂度
                            </p>
                            <p class="text-3xl font-bold text-purple-600">O(n)</p>
                            <p class="text-gray-600 mt-1">栈的最大深度取决于嵌套层数</p>
                        </div>
                    </div>
                </div>
            </div>
        </section>

        <!-- Code Implementation -->
        <section class="mb-16">
            <div class="code-block">
                <div class="code-header flex items-center justify-between">
                    <div class="flex items-center">
                        <i class="fab fa-java text-orange-400 mr-2"></i>
                        <span class="text-gray-300 font-semibold">Java 实现</span>
                    </div>
                    <div class="flex space-x-2">
                        <span class="w-3 h-3 bg-red-500 rounded-full"></span>
                        <span class="w-3 h-3 bg-yellow-500 rounded-full"></span>
                        <span class="w-3 h-3 bg-green-500 rounded-full"></span>
                    </div>
                </div>
                <pre><code class="text-gray-300">public String decodeString(String s) {
    // 使用栈来存储括号前的字符串和重复次数
    Stack&lt;Pair&lt;String, Integer&gt;&gt; stack = new Stack&lt;&gt;();
    
    // 当前正在处理的字符串
    String currString = "";
    // 当前正在处理的数字（重复次数）
    int currNumber = 0;
    
    // 遍历输入字符串的每个字符
    for (char c : s.toCharArray()) {
        if (Character.isDigit(c)) {
            // 如果是数字，计算重复次数（可能是多位数）
            currNumber = currNumber * 10 + (c - '0');
        } else if (c == '[') {
            // 遇到左括号，将当前字符串和重复次数入栈，并重置当前变量
            stack.push(new Pair&lt;&gt;(currString, currNumber));
            currString = "";
            currNumber = 0;
        } else if (c == ']') {
            // 遇到右括号，出栈并构建重复字符串
            Pair&lt;String, Integer&gt; pair = stack.pop();
            String prevString = pair.getKey();
            int repeatTimes = pair.getValue();
            
            // 